package class06;

import java.util.HashMap;

/**
 * @description: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * @time: 2021/7/16 11:20
 * @author: lhy
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length){
            return null;
        }
        HashMap<Integer,Integer> valueIndexMap = new HashMap<>(in.length);
        for (int i = 0; i < in.length; i++) {
            valueIndexMap.put(in[i],i);
        }
        return f(pre,0,pre.length - 1,in,0,in.length - 1,valueIndexMap);
    }

    private TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer,Integer> valueIndexMap) {
        if (l1 > r1){
            return null;
        }
        TreeNode root = new TreeNode(pre[l1]);
        if (l1 == r1){
            return root;
        }
        int i = valueIndexMap.get(pre[l1]);
        root.left = f(pre,l1+1,l1+i-l2,in,l2,i-1,valueIndexMap);
        root.right = f(pre,l1+i-l2+1,r1,in,i+1,r2,valueIndexMap);
        return root;
    }

}
